{
 "metadata": {
  "name": "",
  "signature": "sha256:84c732adb1bf8803e85ba31d5004e28853d38449b52948ce5209eef68e21a014"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Basic Multi-objective optimization features"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In this tutorial we will learn how to use PyGMO to solve multiple-objective optimization problems. In essence we will learn how to use the methods that deal with Pareto-optimality, in particular those of the class population\n",
      "\n",
      "This tutorial assumes an ipython interactive environment. Let us start to define our population:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from PyGMO import algorithm, island, population, problem\n",
      "prob = problem.zdt(1)\n",
      "pop = population(prob, 10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We here make use of first problem of the ZDT benchmark suite and we created a population containing 10 individuals randomly created within the box bounds. Which individuals belong to which preto front? We can immediately see this by typing:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "pop.compute_pareto_fronts()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%matplotlib inline\n",
      "import matplotlib.pyplot as plt\n",
      "\n",
      "pop = population(prob, 100)\n",
      "pop.plot_pareto_fronts()  # This call already plots to default pyplot canvas\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "we have instantiated the algorithm Non-dominated Sorting Genetic Algorithm, able to tackle multi-objective problems, defining the number of generations to 250. In the next line use directly the method evolve of the algorithm to evolve the population. We could have also, similarly, defined an island and use the evolve method of the island:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "algo = algorithm.nsga_II(gen=250)\n",
      "isl = island(algo, pop)\n",
      "isl.evolve(1)\n",
      "isl.population.plot_pareto_fronts()\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "PADE: a parallel MOEA-D algorithm"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In this tutorial we will learn how to use PADE to solve a multi-objective problem. PADE transforms a multi-objective problem into N single-objective ones, where N is the population size. It does that using the Decomposition meta problem. It then solve each problem in parallel using a given single objective algorithm. The population provided at the end of the evolution will be the union of the solutions to each single-objective problem.\n",
      "\n",
      "Let start using PADE to solve the popular multi-objective benchmark problem ZDT1."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from PyGMO import problem, algorithm, population\n",
      "%matplotlib inline\n",
      "import matplotlib.pyplot as plt\n",
      "\n",
      "prob = problem.zdt(1)\n",
      "alg = algorithm.pade()\n",
      "pop = population(prob, 50)\n",
      "pop = alg.evolve(pop)\n",
      "pop.plot_pareto_fronts()\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Each point on the pareto front corresponds to the solution to a single-objective problem. In order for the point to be well spread is then crucial to choose the proper decomposition method and the proper weight vectors. It is possible to do that as follow:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.pade(decomposition=problem.decompose.BI, weights=algorithm.pade.GRID)\n",
      "pop = alg.evolve(pop)\n",
      "pop.plot_pareto_fronts()\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "As we can see the points on the pareto front are much better spread.\n",
      "\n",
      "In the following plots we see how different weight generation methods perform on the 3-objective benchmark problem DTLZ1. First we will use a RANDOM weight generation."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from PyGMO import algorithm, problem, population\n",
      "alg = algorithm.pade(decomposition=problem.decompose.BI, weights=algorithm.pade.RANDOM)\n",
      "prob = problem.dtlz(1)\n",
      "pop = population(prob, 100)\n",
      "pop = alg.evolve(pop)\n",
      "prob.plot(pop)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Let\u2019s now try generating the weight vectors with the GRID method"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.pade(decomposition=problem.decompose.BI, weights=algorithm.pade.GRID)\n",
      "pop = population(prob, 100)\n",
      "pop = alg.evolve(pop)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "As we can see from the error message we cannot use any population size. The error message will suggest us the two accepted values closer to the one we wanted. Let\u2019s then choose 105."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "pop = population(prob, 105)\n",
      "pop = alg.evolve(pop)\n",
      "prob.plot(pop)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "As we can see the front is much better spread. The only drawback of the GRID method is that we are not free to choose any population size. To have a better spread than the one obtained with the RANDOM method but still be able to choose any population size, we can use the LOW_DISCREPANCY method."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.pade(decomposition=problem.decompose.BI, weights=algorithm.pade.LOW_DISCREPANCY)\n",
      "pop = population(prob, 100)\n",
      "pop = alg.evolve(pop)\n",
      "prob.plot(pop)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We now introduce two more interesting features of PADE.\n",
      "\n",
      "It is possible to choose which single-objective algorithm to use to solve each single-objective problem the original problem is decomposed into, in the following way"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.pade(solver=algorithm.jde(50))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Moreover, as said at the beginning of the tutorial, PADE solves the single-objective problems in parallel. It is possible to set how many threads to run. This should be ideally equal to the number of logic cores available in the machine which runs the code."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.pade(max_parallelism=8)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Using NSGA-II, SPEA2 and NS-PSO"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We will now introduce 3 more multi-objective optimization algorithms.\n",
      "\n",
      "Let\u2019s start with NSGA-II. NSGA-II is a non-dominated sorting based multi-objective evolutionary algorithm. It generates offspring with crossover and mutation and select the next generation according to non-dominated sorting and crowding distance comparison. As for PADE it is possible to solve a multi-objective optimization problem with NSGA-II as follow"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from PyGMO import algorithm, problem\n",
      "prob = problem.zdt(1)\n",
      "alg = algorithm.nsga_II()\n",
      "pop = population(prob, 100)\n",
      "pop = alg.evolve(pop)\n",
      "pop.plot_pareto_fronts()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It is possible to specify the number of generations to run the algorithm for, crossover and mutation probability as well as the mutation and crossover distribution index, as follow"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.nsga_II(gen=100, cr=0.95, eta_c=10, m=0.01, eta_m=50)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This will run the NSGA-II algorithms for 100 generations, with a crossover probability of 0.95, mutation probability of 0.01, crossover distribution index of 10 and mutation distribution index of 50.\n",
      "\n",
      "We now introduce NSPSO. Non-dominated Sorting Particle Swarm Optimizer (NSPSO) is a modified version of PSO for multi-objective optimization. It extends the basic ideas of PSO by making a better use of personal bests and offspring for non-dominated comparison. As for PSO it is possible to set:\n",
      "\n",
      "* C1 and C2 (the magnitude of the force to apply towards respectively the personal best and the global best of a particle)\n",
      "* CHI the velocity scaling factor\n",
      "* m_v_coeff the velocity coefficient (determining the maximum allowed particle velocity)\n",
      "* minW and maxW which defines in which range the inertia weight will be adapted throughout the run.\n",
      "\n",
      "Here we see how those parameters can be set when instantiating the algorithm"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.nspso(gen=10, minW=0.4, maxW=1.0, C1=2.0, C2=2.0, CHI=1.0, v_coeff=0.5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "NSPSO selects the global best for each particles among non-dominated particles. The non-dominated particles are sorted according to one niching method (crowding distance, niche count or maxmin) and the leader is selected among the best ones. The parameter leader_selection_range define which fraction of the non-dominated particles to consider for selection as global best.\n",
      "\n",
      "In the following code leader_selection_range is set to 20. That means that the global best for each particle is randomly selected among the top 20% (according to the niching method) non-dominated individuals."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.nspso(leader_selection_range=20)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It is possible to choose between 3 different niching methods: CROWDING DISTANCE, NICHE COUNT and MAXMIN. This can be done as follow:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.nspso(diversity_mechanism=algorithm.nspso.CROWDING_DISTANCE)\n",
      "alg = algorithm.nspso(diversity_mechanism=algorithm.nspso.NICHE_COUNT)\n",
      "alg = algorithm.nspso(diversity_mechanism=algorithm.nspso.MAXMIN)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The last multi-objective optimization algorithm we introduce is SPEA2. In the Strength Pareto Evolutionary Algorithm (SPEA2) the quality of an individual is measured taking into consideration its pareto strength and its distance to its K-th neighbour, where K = sqrt(pop size + archive size). It uses the same mutation and crossover operators of NSGA-II, so as for the former it is possible to specify the number of generations to run the algorithm for, crossover and mutation probability as well as the mutation and crossover distribution index, as follow."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.spea2(gen=100, cr=0.95, eta_c=10, m=0.01, eta_m=50)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "SPEA2 uses an external archive in which are stored the non dominated solutions found so far. The size of the archive is kept constant throughout the run by mean of a truncation operator taking into consideration the distance of each individual to its closest neighbours.\n",
      "\n",
      "It is possible to set the archive size in two ways. If archive_size is set to 0 (which is the default behaviour), then archive size is adapted to be equal to the population which is evolving. In the following case, for example, the archive size will be set equal to 100."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.spea2(archive_size=0)\n",
      "pop = population(prob, 100)\n",
      "pop = alg.evolve(pop)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Otherwise it is possible to set the archive size to any size, up to the population size."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "alg = algorithm.spea2(archive_size=20)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}